{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #舒适的湿度"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: unSuitability"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #舒适的湿度"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "力扣嘉年华为了确保更舒适的游览环境条件，在会场的各处设置了湿度调节装置，这些调节装置受控于总控室中的一台控制器。\n",
    "控制器中已经预设了一些调节指令，整数数组`operate[i]` 表示第 `i` 条指令增加空气湿度的大小。现在你可以将任意数量的指令修改为降低湿度（变化的数值不变），以确保湿度尽可能的适宜：\n",
    "- 控制器会选择 **一段连续的指令** ，从而进行湿度调节的操作；\n",
    "- 这段指令最终对湿度影响的绝对值，即为当前操作的「不适宜度」\n",
    "- 在控制器所有可能的操作中，**最大** 的「不适宜度」即为「整体不适宜度」\n",
    "\n",
    "请返回在所有修改指令的方案中，可以得到的 **最小** 「整体不适宜度」。\n",
    "\n",
    "**示例 1：**\n",
    "> 输入：`operate = [5,3,7]`\n",
    ">\n",
    "> 输出：`8`\n",
    ">\n",
    "> 解释：对于方案 `2` 的 `[5,3,-7]`\n",
    ">操作指令 `[5],[3],[-7]` 的「不适宜度」分别为 `5,3,7`\n",
    ">操作指令 `[5,3],[3,-7]` 的「不适宜度」分别为 `8,4`\n",
    ">操作指令 `[5,3,-7]` 的「不适宜度」为 `1`，\n",
    ">因此对于方案 `[5,3,-7]`的「整体不适宜度」为 `8`，其余方案的「整体不适宜度」均不小于 `8`，如下表所示：\n",
    "![image.png](https://pic.leetcode-cn.com/1663902759-dgDCxn-image.png){:width=650px}\n",
    "\n",
    "**示例 2：**\n",
    "> 输入：`operate = [20,10]`\n",
    ">\n",
    "> 输出：`20`\n",
    "\n",
    "**提示：**\n",
    "- `1 <= operate.length <= 1000`\n",
    "- `1 <= operate[i] <= 1000`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [3aqs1c](https://leetcode.cn/problems/3aqs1c/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [3aqs1c](https://leetcode.cn/problems/3aqs1c/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[5,3,7]', '[10,20]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unSuitability(self, operate: List[int]) -> int:\n",
    "        low, high = 0, 2004\n",
    "        \n",
    "        def check(m: int) -> bool:\n",
    "            m = m + 1\n",
    "            store = [True] * m\n",
    "            comp = [False] * m\n",
    "            \n",
    "            for o in operate:\n",
    "                for i in range(m):\n",
    "                    c1 = (i+o) < m and store[i+o]\n",
    "                    c2 = (i-o) >= 0 and store[i-o]\n",
    "                    comp[i] = c1 or c2\n",
    "                store, comp = comp, store\n",
    "            \n",
    "            return any(store[:m])\n",
    "        \n",
    "        while high > low:\n",
    "            mid = (high + low) // 2\n",
    "            if check(mid): high = mid\n",
    "            else: low = mid + 1\n",
    "        \n",
    "        return low"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unSuitability(self, operate: List[int]) -> int:\n",
    "        low = 1\n",
    "        high = max(operate) * 2\n",
    "        while low < high:\n",
    "            mid = (high + low) // 2\n",
    "            all = 2 ** mid - 1\n",
    "            x = all\n",
    "            for len in operate:\n",
    "                x = ((x << len) | (x >> len)) & all\n",
    "            \n",
    "            if x == 0:\n",
    "                low = mid + 1\n",
    "            else:\n",
    "                high = mid\n",
    "        \n",
    "        return low - 1\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unSuitability(self, operate: List[int]) -> int:\n",
    "        # dp[i][j] 表示前i个数中，前i个数的累计和和前i个数中最小的累计和的差值（最后一个折线末端在y方向和前i个折线y周最低点的差值）\n",
    "        # 向上：dp[i][j + x] = max(j + x,dp[i-1][j])\n",
    "        # 向下：dp[i][j - x] = dp[i-1][j] j-x>=0\n",
    "        #      dp[i][0]  = max(dp[i-1][j]-j+x, dp[i-1][0]) j-x<0\n",
    "        mx = max(operate) * 2\n",
    "        dp0 = [0] + [inf] * mx\n",
    "        for x in operate:\n",
    "            dp1 = [inf] + [inf] * mx\n",
    "            # 从dp1推dp0不方便，因为有些值是不存在的\n",
    "            for j, v in enumerate(dp0):\n",
    "                if v == inf:\n",
    "                    continue\n",
    "                if j + x <= mx:\n",
    "                    dp1[j + x] = min(dp1[j + x], max(j + x, v))\n",
    "                if j >= x:\n",
    "                    dp1[j - x] = min(dp1[j - x], v)\n",
    "                else:\n",
    "                    dp1[0] = min(dp1[0], v + x - j)\n",
    "                dp0 = dp1\n",
    "        return min(dp0)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def unSuitability(self, operate: List[int]) -> int:\n",
    "        mx = max(operate) * 2\n",
    "        pre = [float('inf')] * (mx + 1)\n",
    "        pre[0] = 0\n",
    "        \n",
    "        for x in operate:\n",
    "            dp = [float('inf')] * (mx + 1)\n",
    "            \n",
    "            for j in range(len(pre)):\n",
    "                dis = pre[j]\n",
    "                \n",
    "                if dis == float('inf'):\n",
    "                    continue\n",
    "                \n",
    "                if j + x <= mx:\n",
    "                    dp[j + x] = min(dp[j + x], max(dis, j + x))\n",
    "                \n",
    "                if j >= x:\n",
    "                    dp[j - x] = min(dp[j - x], dis)\n",
    "                else:\n",
    "                    dp[0] = min(dp[0], dis - j + x)\n",
    "            \n",
    "            pre = dp\n",
    "        \n",
    "        return min(pre)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unSuitability(self, operate: List[int]) -> int:\n",
    "        low, high = 0, max(operate) * 2\n",
    "        \n",
    "        def check(m: int) -> bool:\n",
    "            m = m + 1\n",
    "            store = [True] * m\n",
    "            comp = [False] * m\n",
    "            \n",
    "            for o in operate:\n",
    "                for i in range(m):\n",
    "                    c1 = (i+o) < m and store[i+o]\n",
    "                    c2 = (i-o) >= 0 and store[i-o]\n",
    "                    comp[i] = c1 or c2\n",
    "                store, comp = comp, store\n",
    "            \n",
    "            return any(store[:m])\n",
    "        \n",
    "        while high > low:\n",
    "            mid = (high + low) // 2\n",
    "            if check(mid): high = mid\n",
    "            else: low = mid + 1\n",
    "        \n",
    "        return low"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unSuitability(self, operate: List[int]) -> int:\n",
    "        mx = max(operate) * 2\n",
    "        pre = [0] + [inf] * mx\n",
    "        for x in operate:\n",
    "            f = [inf] * (mx + 1)\n",
    "            for j, dis in enumerate(pre):\n",
    "                if dis == inf: continue  # 无效的长度（无法组成）\n",
    "                if j + x <= mx: f[j + x] = min(f[j + x], max(dis, j + x))\n",
    "                if j >= x: f[j - x] = min(f[j - x], dis)\n",
    "                else: f[0] = min(f[0], dis - j + x)\n",
    "            pre = f\n",
    "        return min(pre)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unSuitability(self, nums: List[int]) -> int:\n",
    "        # https://codeforces.com/contest/1579/submission/130462038\n",
    "        # 二分答案\n",
    "        # 对于答案 mid, 存在一系列操作, 极差<=mid?\n",
    "        # 起点0, 低点min,高点max\n",
    "        # 现在进行平移: 低点0, 高点mid,起始点为 z [0,mid]\n",
    "        # 问题转化为: 是否存在起始点为 z , 且一系列操作都不超出[0,mid]的方案\n",
    "        # 设当前起始点集合为 [0,mid] 的所有数,共 mid+1个数\n",
    "        # 对于较大的数z,下一步可以 减去nums[i],来保证在区间\n",
    "        # 对于较小的数z,下一步可以 加上nums[i],来保证在区间\n",
    "        # 对于中间的数z,下一步可以 加减nums[i],可能都超出区间\n",
    "        # 如果存在z, 从起点到终点都有不超出[0,mid]的方案, 则答案有效\n",
    "        def cando(x):\n",
    "            s=(1<<(x+1))-1\n",
    "            rest = s\n",
    "            for c in nums:\n",
    "                s1 = (rest>>c) & s\n",
    "                s2 = (rest<<c) & s\n",
    "                rest=s1|s2 \n",
    "            return rest\n",
    "        # 假设起点为0,下一步的范围即为[-maxnum,maxnum]\n",
    "        # 假设起点< 0,下一步的范围即为[起点,maxnum-abs(起点)]\n",
    "        # 假设起点> 0,下一步的范围即为[-maxnum+abs(起点),起点]\n",
    "        l,r = 1, max(nums)<<1\n",
    "        while l<=r:\n",
    "            x=l+(r-l)//2\n",
    "            if cando(x):\n",
    "                r=x-1\n",
    "            else:\n",
    "                l=x+1\n",
    "        return l\n",
    "    def unSuitability_1(self, nums: List[int]) -> int:\n",
    "        def check(mid: int) -> bool:\n",
    "            mask = (1 << (mid + 1)) - 1\n",
    "            dp = mask\n",
    "            for num in nums:\n",
    "                dp = ((dp << num) | (dp >> num)) & mask\n",
    "            return dp != 0\n",
    "\n",
    "        left, right = 0, sum(nums)  # 实际的上界为 max(nums)*2\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unSuitability(self, operate: List[int]) -> int:\n",
    "        mx = max(operate) * 2\n",
    "        pre = [0] + [inf] * mx\n",
    "        for x in operate:\n",
    "            f = [inf] * (mx + 1)\n",
    "            for j, dis in enumerate(pre):\n",
    "                if dis == inf: continue  # 无效的长度（无法组成）\n",
    "                if j + x <= mx: f[j + x] = min(f[j + x], max(dis, j + x))\n",
    "                if j >= x: f[j - x] = min(f[j - x], dis)\n",
    "                else: f[0] = min(f[0], dis - j + x)\n",
    "            pre = f\n",
    "        return min(pre)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef unSuitability(self, operate):\n",
    "\t\treturn self.bs(operate, max(operate), max(operate) * 2)\n",
    "\t\n",
    "\tdef bs(self, arr, l, r):\n",
    "\t\tif l >= r:\n",
    "\t\t\treturn l\n",
    "\t\tm = (l + r) >> 1\n",
    "\t\tif self.chk(arr, m):\n",
    "\t\t\treturn self.bs(arr, l, m)\n",
    "\t\telse:\n",
    "\t\t\treturn self.bs(arr, m + 1, r)\n",
    "\t\n",
    "\tdef chk(self, arr, k):\n",
    "\t\tlast = {0: 0}\n",
    "\t\tfor x in arr:\n",
    "\t\t\tcur = {}\n",
    "\t\t\tfor big in last:\n",
    "\t\t\t\tif big + x <= k:\n",
    "\t\t\t\t\tcur[big + x] = min(cur.get(big + x, float('inf')), max(0, last[big] - x))\n",
    "\t\t\t\tkey = max(last[big] + x, big - x)\n",
    "\t\t\t\tif key <= k:\n",
    "\t\t\t\t\tcur[key] = min(cur.get(key, float('inf')), last[big] + x, max(big - x, 0))\n",
    "\t\t\tif len(cur) == 0:\n",
    "\t\t\t\treturn False\n",
    "\t\t\tlast = cur\n",
    "\t\treturn True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unSuitability(self, nums: List[int]) -> int:\n",
    "        # 使用状态压缩动态规划检查是否存在一个有效的操作序列\n",
    "        def cando(x):\n",
    "            s=(1<<(x+1))-1\n",
    "            rest = s\n",
    "            for c in nums:\n",
    "                s1 = (rest>>c) & s\n",
    "                s2 = (rest<<c) & s\n",
    "                rest=s1|s2 \n",
    "            return rest\n",
    "        \n",
    "        # 二分查找确定最小的不适宜度\n",
    "        l,r = 1, max(nums)<<1\n",
    "        while l<=r:\n",
    "            x=l+(r-l)//2\n",
    "            if cando(x):\n",
    "                r=x-1\n",
    "            else:\n",
    "                l=x+1\n",
    "        return l\n",
    "    \n",
    "    def unSuitability_1(self, nums: List[int]) -> int:\n",
    "        # 另一种状态压缩动态规划的实现\n",
    "        def check(mid: int) -> bool:\n",
    "            mask = (1 << (mid + 1)) - 1\n",
    "            dp = mask\n",
    "            for num in nums:\n",
    "                dp = ((dp << num) | (dp >> num)) & mask\n",
    "            return dp != 0\n",
    "\n",
    "        left, right = 0, sum(nums)  # 实际的上界为 max(nums)*2\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def unSuitability(self, nums: List[int]) -> int:\n",
    "        # https://codeforces.com/contest/1579/submission/130462038\n",
    "        # 二分答案\n",
    "        # 对于答案 mid, 存在一系列操作, 极差<=mid?\n",
    "        # 起点0, 低点min,高点max\n",
    "        # 现在进行平移: 低点0, 高点mid,起始点为 z [0,mid]\n",
    "        # 问题转化为: 是否存在起始点为 z , 且一系列操作都不超出[0,mid]的方案\n",
    "        # 设当前起始点集合为 [0,mid] 的所有数,共 mid+1个数\n",
    "        # 对于较大的数z,下一步可以 减去nums[i],来保证在区间\n",
    "        # 对于较小的数z,下一步可以 加上nums[i],来保证在区间\n",
    "        # 对于中间的数z,下一步可以 加减nums[i],可能都超出区间\n",
    "        # 如果存在z, 从起点到终点都有不超出[0,mid]的方案, 则答案有效\n",
    "        def cando(x):\n",
    "            s=(1<<(x+1))-1\n",
    "            rest = s\n",
    "            for c in nums:\n",
    "                s1 = (rest>>c) & s\n",
    "                s2 = (rest<<c) & s\n",
    "                rest=s1|s2 \n",
    "            return rest\n",
    "        # 假设起点为0,下一步的范围即为[-maxnum,maxnum]\n",
    "        # 假设起点< 0,下一步的范围即为[起点,maxnum-abs(起点)]\n",
    "        # 假设起点> 0,下一步的范围即为[-maxnum+abs(起点),起点]\n",
    "        l,r = 1, max(nums)<<1\n",
    "        while l<=r:\n",
    "            x=l+(r-l)//2\n",
    "            if cando(x):\n",
    "                r=x-1\n",
    "            else:\n",
    "                l=x+1\n",
    "        return l\n",
    "    def unSuitability_1(self, nums: List[int]) -> int:\n",
    "        def check(mid: int) -> bool:\n",
    "            mask = (1 << (mid + 1)) - 1\n",
    "            dp = mask\n",
    "            for num in nums:\n",
    "                dp = ((dp << num) | (dp >> num)) & mask\n",
    "            return dp != 0\n",
    "\n",
    "        left, right = 0, sum(nums)  # 实际的上界为 max(nums)*2\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unSuitability(self, nums: List[int]) -> int:\n",
    "        def check(mid: int) -> bool:\n",
    "            mask = (1 << (mid + 1)) - 1\n",
    "            dp = mask\n",
    "            for num in nums:\n",
    "                dp = ((dp << num) | (dp >> num)) & mask\n",
    "            return dp != 0\n",
    "\n",
    "        left, right = 0, sum(nums)  \n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def unSuitability(self, operate: List[int]) -> int:\r\n",
    "        mx = max(operate) * 2\r\n",
    "        pre = [0] + [inf] * mx\r\n",
    "        for x in operate:\r\n",
    "            f = [inf] * (mx + 1)\r\n",
    "            for j, dis in enumerate(pre):\r\n",
    "                if dis == inf: continue  # 无效的长度（无法组成）\r\n",
    "                if j + x <= mx: f[j + x] = min(f[j + x], max(dis, j + x))\r\n",
    "                if j >= x: f[j - x] = min(f[j - x], dis)\r\n",
    "                else: f[0] = min(f[0], dis - j + x)\r\n",
    "            pre = f\r\n",
    "        return min(pre)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
